#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;

    ListNode(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    ListNode* head;
public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        clear();
    }

    void clear() {
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* temp = current;
            current = current->next;
            delete temp;
        }
        head = nullptr;
    }

    void createHeadInsert(int arr[], int n) {
        clear();

        for (int i = 0; i < n; i++) {
            ListNode* newNode = new ListNode(arr[i]);
            newNode->next = head;
            head = newNode;
        }
        cout << "头插法创建链表完成，共插入 " << n << " 个元素" << endl;
    }

    void createTailInsert(int arr[], int n) {
        clear();

        if (n == 0) return;

        head = new ListNode(arr[0]);
        ListNode* tail = head;

        for (int i = 1; i < n; i++) {
            ListNode* newNode = new ListNode(arr[i]);
            tail->next = newNode;
            tail = newNode;
        }
        cout << "尾插法创建链表完成，共插入 " << n << " 个元素" << endl;
    }

    bool insert(int position, int value) {
        if (position < 0) {
            cout << "位置不能为负数！" << endl;
            return false;
        }

        ListNode* newNode = new ListNode(value);

        if (position == 0) {
            newNode->next = head;
            head = newNode;
            cout << "在头部插入元素: " << value << endl;
            return true;
        }

        ListNode* current = head;
        int count = 0;

        while (current != nullptr && count < position - 1) {
            current = current->next;
            count++;
        }

        if (current == nullptr) {
            cout << "插入位置 " << position << " 超出链表长度！" << endl;
            delete newNode;
            return false;
        }

        newNode->next = current->next;
        current->next = newNode;
        cout << "在位置 " << position << " 插入元素: " << value << endl;
        return true;
    }

    bool removeByValue(int value) {
        if (head == nullptr) {
            cout << "链表为空，无法删除！" << endl;
            return false;
        }

        if (head->data == value) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            cout << "删除元素: " << value << endl;
            return true;
        }

        ListNode* current = head;
        while (current->next != nullptr && current->next->data != value) {
            current = current->next;
        }

        if (current->next == nullptr) {
            cout << "未找到元素: " << value << endl;
            return false;
        }

        ListNode* temp = current->next;
        current->next = temp->next;
        delete temp;
        cout << "删除元素: " << value << endl;
        return true;
    }

    bool removeByPosition(int position) {
        if (head == nullptr) {
            cout << "链表为空，无法删除！" << endl;
            return false;
        }

        if (position < 0) {
            cout << "位置不能为负数！" << endl;
            return false;
        }
        if (position == 0) {
            ListNode* temp = head;
            head = head->next;
            int value = temp->data;
            delete temp;
            cout << "删除位置 " << position << " 的元素: " << value << endl;
            return true;
        }

        ListNode* current = head;
        int count = 0;

        while (current != nullptr && count < position - 1) {
            current = current->next;
            count++;
        }

        if (current == nullptr || current->next == nullptr) {
            cout << "删除位置 " << position << " 超出链表长度！" << endl;
            return false;
        }

        ListNode* temp = current->next;
        current->next = temp->next;
        int value = temp->data;
        delete temp;
        cout << "删除位置 " << position << " 的元素: " << value << endl;
        return true;
    }

    int findPositionByValue(int value) {
        ListNode* current = head;
        int position = 0;

        while (current != nullptr) {
            if (current->data == value) {
                cout << "元素 " << value << " 在位置: " << position << endl;
                return position;
            }
            current = current->next;
            position++;
        }

        cout << "未找到元素: " << value << endl;
        return -1;
    }

    int findValueByPosition(int position) {
        if (position < 0) {
            cout << "位置不能为负数！" << endl;
            return -1;
        }

        ListNode* current = head;
        int count = 0;

        while (current != nullptr && count < position) {
            current = current->next;
            count++;
        }

        if (current == nullptr) {
            cout << "位置 " << position << " 超出链表长度！" << endl;
            return -1;
        }

        cout << "位置 " << position << " 的元素是: " << current->data << endl;
        return current->data;
    }

    void display() {
        if (head == nullptr) {
            cout << "链表为空！" << endl;
            return;
        }

        ListNode* current = head;
        cout << "链表元素: ";
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) {
                cout << " -> ";
            }
            current = current->next;
        }
        cout << " -> NULL" << endl;
    }

    int getLength() {
        int length = 0;
        ListNode* current = head;
        while (current != nullptr) {
            length++;
            current = current->next;
        }
        return length;
    }
};

#endif